import java.util.*;

/**
 * @Classname BinarySearch 二分查找/折半查找,前提是 列表有序
 * @Description TODO  排序后的列表，根据中间数查找
 *
 * @Date 2021/11/18 13:58
 * @Created K024851
 */
public class BinarySearch {

    public static void main(String[] args) {
        int arr[] = {1,8,10,89,1111,1111,1234};

    }

    public static int binarySearch(int[] arr,int left,int right,int findVal){

        //说明递归了整个数组，但是没有找到
        if (left>right){
            return  -1;
        }
        int mid =(left+right)/2;
        int midVal = arr[mid];

        if (findVal>midVal){
            return  binarySearch(arr,mid+1,right,findVal);
        }
        else if (findVal<midVal){
            return  binarySearch(arr, left, mid-1, findVal);
        } else {
            return mid;
        }
    }

    public static List<Integer> binarySearch2(int[] arr, int left, int right, int findVal){

        if (left>right){
            return  new ArrayList<Integer>();
        }
        int mid =(left+right)/2;
        int midVal = arr[mid];

        if (findVal>midVal){
            return  binarySearch2(arr,mid+1,right,findVal);
        }
        else if (findVal<midVal){
            return  binarySearch2(arr, left, mid-1, findVal);
        } else {

            List<Integer> resIndexlist = new ArrayList<Integer>();
            int temp = mid-1;
            while (true){
                if (temp<0 || arr[temp]!=findVal){
                    break;
                }
                resIndexlist.add(temp);
                temp -=1;
            }
            resIndexlist.add(mid);
            temp = mid+1;

            while (true){
                if (temp>arr.length-1 || arr[temp]!=findVal){
                    break;
                }
                resIndexlist.add(temp);
                temp +=1;
            }


            return resIndexlist;
        }
    }
}
